#include <vector>
#include <stack>
#include <math.h>
class Solution {

public:
    int longestWPI(std::vector<int>& hours) {
        int thr = 8;
        auto len = hours.size();
        int* dp = new int[len+1];
        dp[0] = 0;
        for (int i = 1; i < len+1; i++) {
            dp[i] = dp[i - 1] + (hours[i - 1] > thr ? 1 : -1);
        }
        std::stack<int>stack_;
        for (int i = 0; i < len + 1; i++) {
            if (stack_.empty() || dp[stack_.top()] > dp[i])
                stack_.push(i);
        }
        int res = 0;
        for (int i = len; i >= res; i--) {
            int tmp = -1;
            while (!stack_.empty() && dp[stack_.top()] < dp[i]) {
                tmp = stack_.top();
                res = res > (i - tmp) ? res : i - tmp;
                stack_.pop();
            }
        }
        return res;
    }
};